{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 实现名称                                   | 并发模型                   | 底层数据结构                | 容量特性                   | 核心思路概览                                                 | 典型优势                                                     | 主要限制与代价                                               |\n",
    "| ------------------------------------------ | -------------------------- | --------------------------- | -------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| **Michael & Scott 队列 (MSLockFreeQueue)** | 多生产者 / 多消费者 (MPMC) | 带哨兵节点的单向链表        | 理论上无界（仅受内存限制） | 维护一个始终存在的 dummy 节点，入队在尾指针 `tail` 后面挂新节点，出队从头指针 `head` 的后继取数据，依靠 CAS 链接与移动指针 | 不需预估容量、完全 MPMC、在高并发下公平性好                  | 动态分配频繁；需要安全内存回收（Hazard Pointer/Epoch GC）；若无妥善处理 ABA，会出现逻辑错误 |\n",
    "| **SPSC 环形缓冲队列 (SPSCRingBuffer)**     | 单生产者 / 单消费者 (SPSC) | 固定容量环形数组            | 有界                       | 使用 `head`/`tail` 两个索引绕环推进，利用空槽这一额外位置区分满/空，读写线程各自独占一个索引 | 实现极简、无虚假共享、吞吐和延迟稳定，适合实时流媒体/音频管线 | 仅限单生产者+单消费者；容量需提前设定；不支持阻塞等待        |\n",
    "| **MPSC 环形缓冲队列 (MPSCRingBuffer)**     | 多生产者 / 单消费者 (MPSC) | 固定容量环形数组 + 每槽序号 | 有界                       | 每个生产者通过 CAS/FETCH_ADD 抢占写槽，槽位序号区分“可写/已写”；单消费者顺序读取，并将序号重置回“可写” | 写端具备高扩展性，读端逻辑简洁；缓存局部性好                 | 出队端必须单线程；生产者冲突下需自旋退避；序号操作复杂，需防止溢出 |\n",
    "| **LCR 队列 (LCRQueue)**                    | 多生产者 / 多消费者 (MPMC) | 固定容量环形数组 + 序号槽   | 有界                       | 对每个槽位维护序号，生产者、消费者均用序号比较判断槽状态，通过 CAS 推进 head/tail，类似 LCRQ/LMAX Disruptor 思路 | 真正 MPMC，保持环形队列的缓存友好；吞吐高，尤其适合固定容量的高频数据流 | 序号需与容量配合（通常为 2 的幂）；自旋较多可能导致 CPU 抖动；实现复杂度高，仍需考虑公平性与退避策略 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Michael & Scott 无界队列（MSLockFreeQueue）\n",
    "\n",
    "- **算法核心**\n",
    "  1. 队列初始化时创建一个哨兵节点 `dummy`，`head` 与 `tail` 指向它。\n",
    "  2. 入队：读出尾节点 `tail` 与其 `next`。若 `next == nullptr`（即尾节点确实是最后一个），使用 `CAS` 将 `tail->next` 设为新节点，再尝试用 `CAS` 推进 `tail`。若 `next != nullptr`，说明另外一个线程已经插入节点但尚未移动 `tail`，此时帮助推进 `tail`。\n",
    "  3. 出队：读出 `head`、`tail`、`head->next`。若 `head == tail` 且 `next == nullptr`，表示队列空；若 `head == tail` 但 `next != nullptr`，帮助推进 `tail`；否则读取 `next->value`，再使用 `CAS` 推进 `head`，并将旧 `head` 节点延迟回收。\n",
    "- **关键要点**\n",
    "  - 哨兵节点让入队/出队逻辑对称，避免空队特殊处理。\n",
    "  - `compare_exchange_weak` 在循环中结合自旋实现无锁推进。\n",
    "  - 内存回收必须安全，本示范将旧 `head` 放入退休链表，避免并发释放导致悬空指针；真实系统需使用 hazard pointers 等成熟方案。\n",
    "  - 为降低 ABA 风险，可结合指针标记或引用计数等手段。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单生产者单消费者环形队列（SPSCRingBuffer）\n",
    "\n",
    "- **算法核心**\n",
    "  1. 内部数组大小为 `capacity + 1`，利用空余槽区分满/空。\n",
    "  2. 生产者独占写指针 `tail`：写入元素后将 `tail` 移动至下一个索引。\n",
    "  3. 消费者独占读指针 `head`：读取 `buffer[head]` 后将 `head` 自增。\n",
    "  4. 队满条件：`next_tail == head`；队空条件：`head == tail`。\n",
    "- **关键要点**\n",
    "  - 所有原子操作均使用 `memory_order_relaxed` 搭配 `acquire/release`，保证写入可见性。\n",
    "  - 由于只有单写单读，不存在写写或读读竞争，省去 CAS，自旋仅用于等待对方推进。\n",
    "  - 实际部署中常配合 `pause` 指令或 `std::this_thread::yield()` 减少忙等。\n",
    "  - 适合硬实时或低延迟场景，如音视频 buffer、网络包 pipeline。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多生产者单消费者环形队列（MPSCRingBuffer）\n",
    "\n",
    "- **算法核心**\n",
    "  1. 队列容量向上取 2 的幂，方便使用掩码 `index & mask` 实现环绕。\n",
    "  2. 每个槽位结构 `Slot` 包含实际值 `value` 和一个原子 `sequence`。\n",
    "  3. 生产者：\n",
    "     - 循环读取 `tail`，定位目标槽位，检查 `sequence` 是否等于 `position`。\n",
    "     - 若相等表明槽位可写，尝试 `CAS` 将 `tail` 推进。\n",
    "     - 成功后写入值，将 `sequence` 更新为 `position + 1`，表示可读。\n",
    "  4. 单消费者：\n",
    "     - 读取 `head`，检查槽位序号是否等于 `position + 1`。\n",
    "     - 若相等则读取值，`CAS` 推进 `head`，并把序号重置为 `position + mask + 1`（即回到“可写”状态）。\n",
    "- **关键要点**\n",
    "  - `sequence` 的差值决定槽位状态：\n",
    "    - `seq == pos` → 可写；\n",
    "    - `seq == pos + 1` → 可读；\n",
    "    - 其他情况代表队列满或竞争。\n",
    "  - 生产者之间仍需重试，因此需要适当退避，例如 `yield()` 或指数退避。\n",
    "  - 消费者单线程，避免了读端复杂性和额外同步。\n",
    "  - 常用于 log ring buffer、网络执行器等“多写单读”队列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多生产者多消费者环形队列（LCRQueue）\n",
    "\n",
    "- **算法核心**\n",
    "  1. 同样使用序号槽位，但读写双方均为多线程；`sequence` 逻辑与 MPSC 类似。\n",
    "  2. 生产者：CAS 推进 `tail`，成功占领槽位后写入数据并更新序号。\n",
    "  3. 消费者：CAS 推进 `head`，确认槽位可读后取数据，将序号重置到下一轮可写状态。\n",
    "  4. 由于读写两端都可能竞争，需要双向 CAS 循环与退避策略。\n",
    "- **关键要点**\n",
    "  - 序号不仅标识可读/可写，还承担“第几圈”信息，防止伪满/伪空。\n",
    "  - 容量必须为 2 的幂，确保 `mask` 工作正确。\n",
    "  - 为减少伪共享，可将 `head`、`tail` 放在不同 cache line（示例中可进一步扩展 `struct alignas(64)` 等）。\n",
    "  - 在极高竞争下，建议加入指数退避或锁适配策略，避免 CPU 饱和。\n",
    "  - 经常用于固定容量的任务队列、渲染/音频工作流等需要 MPMC 的场景。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! g++ -O3 lf_queue_benchmark.cpp -lbenchmark -lpthread -o lf_queue_benchmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T03:29:13+08:00\n",
      "Running ./lf_queue_benchmark\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.51, 0.36, 0.37\n",
      "-----------------------------------------------------------------------------------------------------------------------------------\n",
      "Benchmark                                                                         Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------------------------------------------------------------\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time                  720651 ns       154242 ns          959 ThroughputOpsPerSec=66.2889M TotalOps=32.768k\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time                1492313 ns       393673 ns          471 ThroughputOpsPerSec=22.3272M TotalOps=32.768k\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time             1489276 ns       645919 ns          482 ThroughputOpsPerSec=11.8144M TotalOps=16.384k\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time    1595897 ns       708744 ns          439 ThroughputOpsPerSec=10.5653M TotalOps=16.384k\n"
     ]
    }
   ],
   "source": [
    "! ./lf_queue_benchmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T03:29:21+08:00\n",
      "Running ./lf_queue_benchmark\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 1.11, 0.48, 0.41\n",
      "-----------------------------------------------------------------------------------------------------------------------------------\n",
      "Benchmark                                                                         Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------------------------------------------------------------\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time                  637124 ns       144863 ns         1150 ThroughputOpsPerSec=54.8111M TotalOps=32.768k\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time                1682592 ns       395455 ns          414 ThroughputOpsPerSec=19.5632M TotalOps=32.768k\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time             1233476 ns       644614 ns          580 ThroughputOpsPerSec=13.572M TotalOps=16.384k\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time    1653622 ns       754656 ns          435 ThroughputOpsPerSec=10.6392M TotalOps=16.384k\n"
     ]
    }
   ],
   "source": [
    "! ./lf_queue_benchmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T03:28:14+08:00\n",
      "Running ./lf_queue_benchmark\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 1.09, 0.50, 0.42\n",
      "------------------------------------------------------------------------------------------------------------------------------------------\n",
      "Benchmark                                                                                Time             CPU   Iterations UserCounters...\n",
      "------------------------------------------------------------------------------------------------------------------------------------------\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time_mean                    638664 ns       152221 ns            5 ThroughputOpsPerSec=51.0306M TotalOps=32.768k\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time_median                  632260 ns       151890 ns            5 ThroughputOpsPerSec=52.9659M TotalOps=32.768k\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time_stddev                   16384 ns         3977 ns            5 ThroughputOpsPerSec=8.95978M TotalOps=0\n",
      "BM_SPSCQueue<Common::SPSCRingBuffer<int>>/16384/manual_time_cv                        2.57 %          2.61 %             5 ThroughputOpsPerSec=17.56% TotalOps=0.00%\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time_mean                  1674762 ns       400704 ns            5 ThroughputOpsPerSec=18.3073M TotalOps=32.768k\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time_median                1675886 ns       394283 ns            5 ThroughputOpsPerSec=18.0989M TotalOps=32.768k\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time_stddev                  12556 ns        13983 ns            5 ThroughputOpsPerSec=839.33k TotalOps=0\n",
      "BM_MPSCQueue<Common::MPSCRingBuffer<int>>/4/4096/manual_time_cv                       0.75 %          3.49 %             5 ThroughputOpsPerSec=4.58% TotalOps=0.00%\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time_mean               1233412 ns       658240 ns            5 ThroughputOpsPerSec=13.3709M TotalOps=16.384k\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time_median             1233158 ns       652357 ns            5 ThroughputOpsPerSec=13.467M TotalOps=16.384k\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time_stddev               10095 ns        15350 ns            5 ThroughputOpsPerSec=383.241k TotalOps=0\n",
      "BM_BoundedMPMCQueue<Common::LCRQueue<int>>/4/4/2048/manual_time_cv                    0.82 %          2.33 %             5 ThroughputOpsPerSec=2.87% TotalOps=0.00%\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time_mean      1637653 ns       752555 ns            5 ThroughputOpsPerSec=9.28474M TotalOps=16.384k\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time_median    1646402 ns       750910 ns            5 ThroughputOpsPerSec=9.67707M TotalOps=16.384k\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time_stddev      15209 ns        16162 ns            5 ThroughputOpsPerSec=757.827k TotalOps=0\n",
      "BM_UnboundedMPMCQueue<Common::MSLockFreeQueue<int>>/4/4/2048/manual_time_cv           0.93 %          2.15 %             5 ThroughputOpsPerSec=8.16% TotalOps=0.00%\n"
     ]
    }
   ],
   "source": [
    "! ./lf_queue_benchmark --benchmark_repetitions=5 --benchmark_report_aggregates_only=true"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
